#include "quickSort2.h"
#include "directSort3.h"
#define CutOff (2)

static void Swap(ElementType *a, ElementType *b)
{
    ElementType tmp;
    tmp = *b;
    *b = *a;
    *a = tmp;
}

ElementType Midian3(ElementType A[], int Left, int Right)
{
    int Center = (Left + Right) / 2;

    if (A[Left] > A[Center])
        Swap(A + Left, A + Center);
    if (A[Left] > A[Right])
        Swap(A + Left, A + Right);
    if (A[Center] > A[Right])
        Swap(A + Center, A + Right);

    //mov pivot to the left of right
    Swap(A + Center, A + Right - 1);
    return A[Right - 1];
}

void QSort(ElementType A[], int Left, int Right)
{
    if (Right - Left > CutOff)
    {
        //选取枢纽元，并将枢纽元移到最右侧值的左侧
        ElementType Pivot;
        int i, j;
        Pivot = Midian3(A, Left, Right);
        i = 0;
        j = Right - 1;
        for (;;)
        {
            //尝试交换i和j的数据直到i移动到j的右侧，此时i的数据必定大于枢纽元
            while (A[++i] < Pivot)
                ;
            while (A[--j] > Pivot)
                ;
            if (i < j)
            {
                Swap(A + i, A + j);
            }
            else
            {
                break;
            }
        }
        Swap(A + i, A + Right - 1);
        QSort(A, Left, i - 1);
        QSort(A, i + 1, Right);
    }
    else
    {
        InsertionSort(A + Left, Right - Left + 1);
    }
}
void QuickSort(ElementType A[], int n)
{
    QSort(A, 0, n - 1);
}